# -*- coding:utf8 -*-

## 加载包
from __future__ import print_function


class Edit_Distance(object):
    '''
    编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
    许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
    '''

    def __init__(self):
        '''
        要求如下：
        1. 利用oschina的git功能，我们四个直接在这个文件中进行编辑。
        2. 输入是两个句子：sm 和 sn
        3. 输出是两个句子的编辑距离
        4. 大家写好后，在下面自己写测试方法，并在主方法中执行
        '''
        print("Caculating edit distance...")

    def min_edit_dist(self, sm, sn):
        '''
        reference url: http://blog.csdn.net/chichoxian/article/details/53944188
        :param sm: first sentence
        :param sn: second sentence
        :return: the distance between this two sentences
        '''
        sm = sm.decode('utf8')
        sn = sn.decode('utf8')

        m, n = len(sm) + 1, len(sn) + 1

        # create a matrix (m*n)

        matrix = [[0] * n for i in range(m)]

        matrix[0][0] = 0
        for i in range(1, m):
            matrix[i][0] = matrix[i - 1][0] + 1

        for j in range(1, n):
            matrix[0][j] = matrix[0][j - 1] + 1

        for i in range(m):
            print(matrix[i])

        print("********************")

        for i in range(1, m):
            for j in range(1, n):
                if sm[i - 1] == sn[j - 1]:
                    cost = 0
                else:
                    cost = 1

                matrix[i][j] = min(matrix[i - 1][j] + 1, matrix[i][j - 1] + 1, matrix[i - 1][j - 1] + cost)

        for i in range(m):
            print(matrix[i])

        return matrix[m - 1][n - 1]

def test_min_edit_dist():
    edit_distance = Edit_Distance()
    mindist = edit_distance.min_edit_dist("我是贺国秀",
                                          "他是贺国考，你是谁？")
    print(mindist)

if __name__ == '__main__':
    test_min_edit_dist()